#define _CRT_SECURE_NO_WARNINGS 1
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

TreeNode* ans;
class Solution {
public:

    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr)return false;
        bool l = dfs(root->left, p, q);
        bool r = dfs(root->right, p, q);
        if ((l && r) || ((p->val == root->val || q->val == root->val))) {
            ans = root;
        }
        return l || r || (root->val == p->val || root->val == q->val);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        ans = nullptr;
        dfs(root, p, q);
        return ans;
    }
};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

TreeNode* ans;

class Solution {
public:
    unordered_map<int, TreeNode*> fa;
    unordered_map<int, bool> st;
    void dfs(TreeNode* root) {
        if (root->left) {
            fa[root->left->val] = root;
            dfs(root->left);
        }
        if (root->right) {
            fa[root->right->val] = root;
            dfs(root->right);
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        fa[root->val] = nullptr;
        dfs(root);

        TreeNode* cur = p;
        while (cur) {
            st[cur->val] = true;
            cur = fa[cur->val];
        }

        cur = q;
        while (cur) {
            if (st[cur->val])return cur;
            cur = fa[cur->val];
        }
        return root;
    }
};